﻿/*
题目：完成旅途的最少时间

给你一个数组 time ，其中 time[i] 表示第 i 辆公交车完成 一趟旅途 所需要花费的时间。

每辆公交车可以 连续 完成多趟旅途，也就是说，一辆公交车当前旅途完成后，可以 立马开始 下一趟旅途。每辆公交车 独立 运行，也就是说可以同时有多辆公交车在运行且互不影响。

给你一个整数 totalTrips ，表示所有公交车 总共 需要完成的旅途数目。请你返回完成 至少 totalTrips 趟旅途需要花费的 最少 时间。

https://leetcode.cn/problems/minimum-time-to-complete-trips/description/?envType=daily-question&envId=2024-10-05
*/

#include <iostream>
#include <string>
#include <vector>
#include <list>
#include "TreeNode.hpp"
#include "ListNode.hpp"
#include <map>
#include <set>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <functional>

using namespace std;

class Solution {
public:
    // 每个线程独立运行，求完成旅途的最少时间
    long long minimumTime(vector<int>& time, int tar) {
        // 二分答案 ?
        long long left = 0, right = time[0] * (long long)tar;
        while (left <= right) {
            long long mid = left + ((right - left) >> 1);
            long long res = howMany(time, mid);

            if (res >= tar) {
                right = mid - 1;
            }
            else {  // res < tar
                left = mid + 1;
            }
        }

        return left;
    }

    long long howMany(const vector<int>& time, long long v) {
        long long res = 0;
        for (auto e : time) {
            res += v / e;
        }
        return res;
    }
};